package cn.chen.数据结构.二叉树.赫夫曼编码;

import java.io.*;
import java.util.*;

public class HuffmanCode {

    // 用于存储编码表的集合
    private Map<Byte,String> map=new HashMap<>();

    // 用于获取编码表的一个辅助缓冲区
    private StringBuilder sb=new StringBuilder();

    // 对文件进行解压
    public void onZipFile(String zipFile,String dstFile){

        FileInputStream is=null;
        ObjectInputStream ois=null;
        FileOutputStream os=null;

        try{

            is=new FileInputStream(zipFile);
            ois=new ObjectInputStream(is);  // 将对象输入流与文件输入流进行关联，压缩的时候将压缩byte与编码表都用对象写入了文件，所以这里需要使用对象输入流将两者读出来

            // 按照存入的顺序，读取压缩后的byte与编码表
            byte[] codeByte=(byte[])ois.readObject();
            Map<Byte,String> codeMap=(Map<Byte,String>)ois.readObject();
            System.out.println(new String(codeByte));
            System.out.println(codeMap);

            // 解压
            byte[] yuan = noZip(codeByte, codeMap);

            os=new FileOutputStream(dstFile);
            os.write(yuan); // 解压后的数据写入文件
        }
        catch (Exception e){

            System.out.println(e.getMessage());
        }
        finally {

            if(os!=null) {
                try {
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if(ois!=null){

                try {
                    ois.close();
                    if(is!=null)
                        is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

        }
    }
    // 对文件进行压缩
    /**
     * @param srcFile   希望压缩的文件的全路径
     * @param dstFile   压缩后的文件存放的路径
     */
    public void zipFile(String srcFile,String dstFile){

        FileInputStream is=null;
        FileOutputStream os=null;
        ObjectOutputStream oos=null;    // 对象输出流

        try{

            is=new FileInputStream(srcFile);
            // 创建一个和源文件同大小的byte数组
            byte[] yuan=new byte[is.available()];   // available 方法就是获取文件的大小

            // 读取文件
            is.read(yuan);

            byte[] codeByte = huffmanZip(yuan); // 将文件压缩，并且返回压缩后的byte数组

            os=new FileOutputStream(dstFile);
            oos=new ObjectOutputStream(os); // 将对象输出流，与文件输出流进行关联

            oos.writeObject(codeByte);  // 将压缩后的byte数组写入压缩文件
            oos.writeObject(map);       // 将编码表也写入压缩文件，不写进去解压文件就会出现问题。
        }
        catch (Exception e){

            System.out.println(e.getMessage());
        }
        finally {

            if(is!=null){

                try {
                    is.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            if(oos!=null){

                try {
                    oos.close();
                    if(os!=null){

                        os.close();
                    }
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }



    // 将数据解压
    public byte[] huffmanNoZip(byte[] byteCode){

        if(map.size()==0){  // 判断编码表是否有数据，如果没有数据，就没有进行编码，就不能进行解压

            System.out.println("没有编码表，不能解码");
            return null;
        }
        return noZip(byteCode,map);
    }

    /**
     * @param byteCode  赫夫曼编码得到的字节数组
     * @param mapCode   赫夫曼编码表 map
     * @return          就是原来字符串对应的数组
     */
    private byte[] noZip(byte[] byteCode,Map<Byte,String> mapCode){

        // 1、 先得到赫夫曼编码得到的字节数组转成的二进制的字符串
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<byteCode.length;i++){

            boolean flag=!(i==byteCode.length-1);  // 如果是最后一个，就不需要补高位，就设置为false
            sb.append(byteToBitString(flag,byteCode[i]));
        }

        // 2、 将字符串按照 执行的赫夫曼编码进行解码
        // 将赫夫曼编码表调转（key与value互换），因为要反向查
        Map<String,Byte> mapDeCode=new HashMap<>();
        for(Map.Entry<Byte,String> m:mapCode.entrySet()){

            mapDeCode.put(m.getValue(),m.getKey());
        }

        // 创建一个集合，存放byte
        // 将反编码表 与数据进行匹配 解码
        List<Byte> list=new ArrayList<>();
        StringBuilder sb2=new StringBuilder();
        for(int i=0;i<sb.length();i++){

            sb2.append(sb.substring(i,i+1));    // 取出一个，并且添加到缓冲区中
            Byte b = mapDeCode.get(sb2.toString());
            if(b==null) // 没有匹配的
                continue;
            else {    // 有匹配的
                list.add(b);
                sb2.delete(0,sb2.length()); // 清空缓冲区
            }
        }
        // for循环结束后，list中就存放了所有的字符i like like like java do you like a java

        // 吧list中的数据放入到byte数组中并返回
        byte[] b=new byte[list.size()];
        for(int i=0;i<b.length;i++){

            b[i]=list.get(i);
        }
        return b;
    }

    // 将byte转成一个二进制的字符串
    /**
     * @param flag  用来标识是否需要补高位，true就要补，false就不需要补,最后一个字节不需要补高位
     * @param b     需要转的byte
     * @return      对应的二进制的字符串（注意是按照补码返回的）
     */
    public String byteToBitString(boolean flag,byte b){

        int temp=b; // 将b转成int类型

        // 正数我们还需要补高位，
        if(flag)
            temp|=256;  // 256 1 0000 0000 | 0000 0001 = 1 0000 0001

        String str=Integer.toBinaryString(temp);    //返回temp对应的二进制的补码

        if(flag)
            return str.substring(str.length()-8);   // 截取倒数8位
        else
            return str;
    }

    // 编码的方法
    public byte[] huffmanZip(byte[] bytes){

        Map<Byte,String> mapCodes=getCodes(createHuffmanTree(getNodes(bytes)));
        return zip(bytes,mapCodes);
    }

    // 将数据用哈夫曼编码表进行编码，然后返回编码之后的数据的byte数组。
    private  byte[] zip(byte[] lod,Map<Byte,String> mapCodes){

        StringBuilder sb=new StringBuilder();
        for(byte l:lod){    // l就是编码表中的key，对应的就是编码（value） lod就是要编码的字符串的byte数组

            sb.append(mapCodes.get(l));
        }
        // 得到的编码之后的1010100010111111110010001011111111001000101111111100100101001101110001110000011011101000111100101000101111111100110001001010011011100

        // 将得到的编码转成byte[]数组
        // 统计返回byte[]的长度
        int len=sb.length()%8==0 ? sb.length()/8 : sb.length()/8+1; // 利用三元运算符，如果能整除8，就是/8的结果，不能整除就是/8+1

        byte[] newByte=new byte[len];

        int index=0;
        for(int i=0;i<sb.length();i+=8){

            String strByte;     // 将每8位截取出来

            if(i+8>sb.length()) // 判断i+8是否超过sb长度
                strByte=sb.substring(i);    // 直接从i截取到末尾
            else
                strByte = sb.substring(i,i+8);

            // 这里是将二进制 转成10进制 然后再将10进制的int类型转成byte类型
            newByte[index++]=(byte)Integer.parseInt(strByte,2); // 将8位转成一个byte数据。
        }
        return newByte;
    }

    // 获取哈夫曼编码表
    public Map<Byte,String> getCodes(Node node){

        if(node==null)
            return null;
        getCodes(node,"",sb);
        return map;
    }

    /**5
     * @param node  传入的结点
     * @param code  路径，左边为0，右边为1
     * @param sb    用于拼接路径
     */
    private void getCodes(Node node ,String code,StringBuilder sb){

        StringBuilder sb2 = new StringBuilder(sb);
        sb2.append(code);

        if(node==null)  // 结点为空
            return;

        if(node.value!=null) // 判断结点是否是叶子结点

            // 是叶子结点
            map.put(node.value,sb2.toString());
        else {  // 不是叶子节点

            // 向左递归 左边路径是0
            getCodes(node.left,"0",sb2);
            // 向右递归 右边路径是1
            getCodes(node.right,"1",sb2);
        }
    }

    // 前序遍历
    public void preOrder(Node root){

        if(root==null)
            return;

        if(root.left==null&&root.right==null)   // 只打印叶结点
            System.out.println(root);

        preOrder(root.left);
        preOrder(root.right);
    }

    // 构建赫夫曼树
    /**
     * @param nodes 要创建哈弗曼树的list集合
     * @return      创建好的哈弗曼树的根结点
     */
    public Node createHuffmanTree(List<Node> nodes){

        while (nodes.size()>1){

            Collections.sort(nodes);    // 排序

            // 获取第一个元素，第二个元素
            Node leftNode = nodes.get(0);
            Node rightNode = nodes.get(1);

            // 创建新节点
            Node parent = new Node(null,leftNode.weight + rightNode.weight);

            parent.left=leftNode;
            parent.right=rightNode;

            // 从集合中删除处理过的节点
            nodes.remove(leftNode);
            nodes.remove(rightNode);

            // 将新节点添加到集合中
            nodes.add(parent);
        }
        // 循环结束之后，集合中只有一个元素，就是创建的赫夫曼树的头结点
        return nodes.get(0);
    }

    // 将byte数组，转换成一个list数据
    public List<Node> getNodes(byte[] bytes){

        List<Node> nodes=new ArrayList<>();

        Map<Byte,Integer> map=new HashMap<>();

        // 存储每个byte出现的次数 map-->[key , value]
        for(byte b:bytes){

            Integer count = map.get(b);

            if(count==null)    // 还没有该字符存放
                map.put(b,1);   // 将该字符添加到集合中，初始次数为1
            else
                map.put(b,count+1); // 将该字符的次数+1
        }

        // 从map中获取键和值 创建Node
        Set<Byte> byteSet = map.keySet();
        for(Byte b:byteSet){

            nodes.add(new Node(b,map.get(b)));
        }
        return nodes;
    }

}
